Various programmable logic architectures are known, including, for example, the programmable logic device ("PLD"), the programmable logic array ("PLA"), and programmable array logic ("PAL.TM."). Wherein there are many differences between the various architectures, each of the PLD, PLA, and
architectures typically includes a set of input conductors directly coupled as inputs to an array of logical AND gates ("product term array"), the outputs of which, in turn, act as inputs to another portion of the logic device.
The product term array is often fully programmable, which typically results in 1) each logical AND gate of the product term array having as many inputs as there are input conductors, 2) an array of programmable switches or elements that allow a programmer to selectively enable and disable the use of each input conductor as an input term for each logical AND gate, and 3) a multiplicity of conductors each of which is routed from one programmable element to one input of a logical AND gate. The total number of programmable elements is typically equal to the number of input conductors multiplied by the number of logical AND gates, and each input conductor is capable of being connected to each logical AND gate. A fully programmable product term array has "full connectability" because each input condutor of the product term array can be coupled to each logical AND gate of the product term array.
For complex programmable logic devices ("CPLDs"), wherein the set of input conductors and the set of logical AND gates to which they connect are both quite large compared to prior PLDs, PALs.TM., and PLAs, maintaining the full connectability of the product term array for each input conductor becomes impractical. First, to maintain full connectability, the size of the input field of each logical AND gate in the product term array must increase for each input conductor that is added. Second, the addition of a single input conductor requires the addition of a number of programmable elements equal to the total number of logical AND gates, one for each logical AND gate. Third, the total number of conductors that are routed from the programmable elements to the AND gates increases as the number of programmable elements increases. All of these consequences of attempting to maintain full connectability for CPLDs result in a large increase in die space for the product term array without a proportionate increase in functionality over the less complex PLD.
One solution is to interpose a connection circuit that is not fully connectable between the set of input conductors and the product term array of a logic block, wherein the inputs of the connection circuit are coupled to the input conductors of the CPLD and the outputs of the connection circuit are coupled to the inputs of the product term array of a logic block. One such connection circuit is associated with each CPLD logic block and provides unique connection between CPLD inputs and the product term array inputs of the associated logic block. Typically, this connection circuit allows only a subset of the CPLD inputs to be connected to the product term array inputs.
Early CPLDs implement this connection circuit as a programmable, fully populated cross-point matrix similar to that used in a fully programmable product term array. Each input conductor of the connection circuit is connected to a number of programmable elements equal to the number of output conductors of the connection circuit, wherein each programmable element is capable of providing a unique connection between the input conductor and one of the output conductors. This connection circuit guarantees a route for every possible combination of input signals up to the total number of output conductors of the front end connection, regardless of the ordering of the combination. A fully populated cross-point matrix may thus be said to have "full connectability," wherein the term "connectability" denotes the ability of the connection circuit to connect an input conductor of the connection circuit to the output conductors of the connection circuit. A "fully connectable" connection circuit is one that can connect every input conductor to every output conductor.
This early approach is very inefficient. First, the number of programmable elements required for each connection circuit is equal to the total number of CPLD input conductors, n.sub.in, multiplied by the number of output conductors, n.sub.out, for the connection circuit, wherein n.sub.out is typically equal to the number of input terms for the product term array of the associated logic block. As a CPLD typically implements two or more connection circuits, this approach requires large amounts of die area.
Second, of the n.sub.in programmable elements connected to any one of the n.sub.out output conductors, only one of the programmable elements is ever programmed, regardless of the input signals selected for routing through the connection circuit. Otherwise, two or more input signals may be shorted together. Thus, the maximum number of programmable elements that are ever used to route any combination of input signals through a fully populated cross-point matrix is n.sub.out. This means that the maximum percentage of programmable elements that are used for any one connection circuit is equal to (1/n.sub.in). Therefore, the amount of die space required to implement the fully connectable cross-point matrix is excessive in light of underutilization of the programmable elements. The inefficiency of this early approach is only emphasized when the number n.sub.in of CPLD inputs increases.
An alternative connection circuit provides full connectability while requiring less "connectivity" than the fully populated cross-point matrix. The term "connectivity" refers to the total number of programmable elements provided by a connection circuit. This alternative connection circuit uses a number n.sub.out of n.sub.in :1 multiplexors, wherein the output of each multiplexor is connected to an output conductor of the connection circuit. As each multiplexor requires only (log n.sub.in /log2) programmable elements, the total number of programmable elements (the connectivity) for a fully connectable multiplexor array is reduced to n.sub.out multiplied by (log n.sub.in /log2). Wherein this results in some savings of die space over the fully connectable cross-point matrix, the die space requirements are still excessive, especially when the number n.sub.out of CPLD input signals increases.
To further reduce the amount of semiconductor die area needed for a connection circuit, the connectivity of the connection circuit may be further reduced by providing even fewer programmable elements. This reduction in connectivity results in connection circuits that are not fully connectable, which means that every input conductor of the connection circuit cannot be connected to every output conductor of the connection circuit. The level of connectability for a connection circuit is related to the level of "routability" of the connection circuit. For purposes of discussion, the term "routability" denotes the probability that the connection circuit can provide a route for any given combination of input signals from the input conductors to the output conductors of the connection circuit. The routability of a connection circuit tends to increase with the connectability of the connection circuit.
Because every input conductor can no longer be connected to every output conductor, the number of "routes" through the connection circuit for a particular combination of input signals may be reduced when compared to fully connectable connection circuits. So long as a connection circuit provides at least one route for every combination of n input signals, the connection circuit is "fully routable" or "100% routable." If no route can be provided for a particular combination of input signals, the connection circuit is not fully routable. Fully connectable connection circuits have "maximum" routability as they provide a route for every permutation of n.sub.out input signals.
Connectivity for a multiplexor array is reduced by reducing the width of the input field for each multiplexor such that the number of input conductors that are coupled to each multiplexor is less than the total number n.sub.in of input conductors for the connection circuit. So long as each input signal is provided with at least one chance to route, i.e., each input conductor is connected to at least one multiplexor, a successful routing for a particular logic function can be achieved regardless of the routability of the connection circuit. For such a constrained multiplexor, providing a route for a particular logic function may require a carefully chosen pin assignment for the CPLD such that the desired combination of input signals are connected to input conductors that have a route through the connection circuit to the output conductors. If the particular logic function is changed at a later time, the same pin assignment may not be able to provide a route for the selected combination of input signals for the altered logic function. This can have disastrous consequences for a system designer which has already manufactured volume quantities of printed circuit boards based on the prior pin assignment.
To better ensure that pin assignments do not have to be altered when a logic function is altered, the routability of the connection circuit should be maximized. As described above, a greater level of connectability for a connection circuit tends to result in a greater level of routability for that connection circuit. However, a greater level of connectability requires a greater level of connectivity, and more die area is consumed, which typically results in higher device cost and slower device speeds. The challenge is to find the optimum balance point between the connectivity, connectability, and routability of a connection circuit.